package com.test.daily.leetcode.y2022.m01.day0104;

import java.util.Arrays;

/**
 * CatMouseGame
 *
 * @author Tom on 2022/1/4
 */
public class Code01_CatMouseGame {
    // 老鼠赢
    static final int MOUSE_WIN = 1;
    // 猫赢
    static final int CAT_WIN = 2;
    // 平局
    static final int DRAW = 0;
    // 棋盘上的位置数量
    int n;
    // 边数组
    int[][] graph;
    // 动态表的数组
    //  猫走过n个点
    // 老鼠走n个点
    // 总共走了多少轮
    int[][][] dp;

    public int catMouseGame(int[][] graph) {
        this.n = graph.length;
        this.graph = graph;
        this.dp = new int[n][n][n * 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 先把所有的dp表填充成-1
                // 如果不等于-1.则代表之前计算过
                // 如果等于-1, 则代表之前未计算过
                Arrays.fill(dp[i][j], -1);
            }
        }
        // 返回老鼠在0位置,猫在2位置, 从第0轮开始的走的最后结果
        return getResult(1, 2, 0);
    }
    // mouse 老鼠在的位置
    // cat 猫在的位置
    // turns 走了多少轮,猫和老鼠都计算
    public int getResult(int mouse, int cat, int turns) {
        // 如果走过了2n轮
        // 下一步则需要继续走,
        // 此时走下去就是会回到原来的位置
        // 则出现平局
        if (turns == n * 2) {
            return DRAW;
        }
        // 如果小于0, 则未计算过
        if (dp[mouse][cat][turns] < 0) {
            // 如果老鼠来到0位置,
            // 老鼠赢
            if (mouse == 0) {
                dp[mouse][cat][turns] = MOUSE_WIN;
                // 如果老鼠和猫来到同一位置
                // 猫赢
            } else if (cat == mouse) {
                dp[mouse][cat][turns] = CAT_WIN;
                // 否则继续走
            } else {
                getNextResult(mouse, cat, turns);
            }
        }
        // 返回上述递归操作生成的dp表的对应的结果
        return dp[mouse][cat][turns];
    }
    // 继续走下一步的结果
    // mouse 代表老鼠来到的位置
    // cat 代表猫来到的位置
    // turns 走了多少轮
    public void getNextResult(int mouse, int cat, int turns) {
        // 判断是轮到猫走还是老鼠走
        int curMove = turns % 2 == 0 ? mouse : cat;
        // 默认是自己输了
        int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
        int result = defaultResult;
        // 可以去哪些位置
        int[] nextNodes = graph[curMove];
        // 来到next这个点
        for (int next : nextNodes) {
            // 猫不能进0位置
            if (curMove == cat && next == 0) {
                continue;
            }
            // 如果是猫走,下一步猫要去的位置;老鼠位置不变
            int nextMouse = curMove == mouse ? next : mouse;
            // 如果是老鼠走,下一步老鼠去的位置;猫位置不变
            int nextCat = curMove == cat ? next : cat;
            // 拿到走完下一步的结果
            int nextResult = getResult(nextMouse, nextCat, turns + 1);
            // 如果状态不是输的状态,
            if (nextResult != defaultResult) {
                result = nextResult;
                // 如果不是平局,则肯定是赢的状态,
                if (result != DRAW) {
                    break;
                }
            }
        }
        // 更新dp表
        dp[mouse][cat][turns] = result;
    }
}
